package 力扣.树.前序遍历;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }
    public TreeNode(int _val) {
        val = _val;
    }
}
public class 遍历 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = null;
        List<Integer> integers = preOrder2(root);
    }
    private  void  preOrder(TreeNode root,List<Integer> ans){
        if (root == null){
            return;
        }
        ans.add(root.val);
        preOrder(root.left,ans);
        preOrder(root.right,ans);


    }
     private  static List<Integer>  preOrder2(TreeNode root){
         ArrayList<Integer> ans = new ArrayList<>();
         Stack<TreeNode> stack = new Stack<>();
         while (root != null || !stack.isEmpty()){
             while (root != null){
                 stack.add(root);
                 ans.add(root.val);
                 root = root.left;
             }
             root = stack.pop();
             root = root.right;
         }
         return ans;
    }

    private static  List<Integer> preOrder3(TreeNode root){
        List<Integer> ans = new ArrayList<>();
        if (root == null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null){
            while ( root!= null){
                stack.add(root);
                ans.add(root.val);
                root = root.left;
            }
            TreeNode treeNode = stack.pop();
            root = treeNode.right;
        }
        return ans;
    }
}





